An Autonomous system (AS) typically is a network which has a single and clearly defined routing policy, as described in IETF, Network Working Group, RFC 1930. An AS may include a small enterprise network, a university network, a national or an intercontinental Internet service providers (ISP). The Internet e.g. is composed of multiple ASes as being a connection of independent networks varying in size.
Autonomous systems (AS) exchange IP traffic with other ASes according to a hierarchical structure. The interconnection between any two autonomous systems typically falls into one of three categories:                The customer-to-provider category, where an AS customer receives traffic transmitted from the rest or part of the Internet from a larger AS provider;        The peer-to-peer category, where two ASes exchange traffic between themselves and their customers, but do not exchange traffic from or to their providers or other peers; and        The sibling-to-sibling category, where two ASes belong to the same organization and exchange IP traffic without any restrictions between their providers, customers, peers or other siblings.        
Autonomous systems (AS) relationships have well-defined restrictions on how IP traffic between two ASes is exchanged, including:                In exporting routes to a provider or a peer, an autonomous system advertises its local routes and routes received from customers and siblings ASes only;        In exporting routes to a customer or a sibling, an AS advertises all its routes, including local routes and routes received from all the AS neighbors.        
From these restrictions a valley-free routing model is derived as described in Lixin Gao, “On Inferring Autonomous System Relationship in the Internet”, in IEEE/ACM Trans on Networking, December 2001, page 5. The valley-free routing model states that any path that is used for routing packets between autonomous systems (AS) of an AS topology is valley-free. A valley-free path is a hierarchical structure and is composed of: an uphill segment of zero or more customer-to-provider or sibling-to-sibling links, followed by zero or one peer-to-peer link, followed by a downhill segment of zero or more provider-to-customer or sibling-to-sibling links.
As a result of the AS relationships between any pair of ASes, the calculation of a valley-free shortest path between any two autonomous systems requires taking into account the restrictions on the IP traffic flow following the valley-free path.
In Z. M. Mao, et. al., “On AS-level path interference”, in ACM SIGMETRICS, 2005, page 4, a method for calculating the valley-free shortest path is proposed. The method requires an extended processing time, including an exhaustive search algorithm of O(V4), wherein V is the number of nodes in a first graph representing an AS topology.
Therefore a way of efficiently calculating a valley-free shortest path between a first and a second autonomous system is desired.